package com.wyr.leetcode.step2.dp;

import java.util.Random;

/**
 * 我们出了一个复杂变体，要求每天都必须卖出，不允许持股过夜，初始资金50，计算最大收益，完全不知道状态方程和总利润如何处理
 * 1.每天收盘前，你必须卖掉所有股票，这样你可以带着所有现金进入第二天的交易。
 * 2.每天你交易的次数是有限的，最多次数不能超过每天股票价格时刻的数量*10%并取整数(比如，如果每天给你109个时刻的价格，那么每天最多交易10次)。
 * 3.你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)
 * 4.要按先买后卖的顺序交易，即你不能用后面的价格买入，再用前面的价格卖出
 */
public class MaxProfitVITest {

    public int maxProfitWithInitialCapitalAndLimit(int[] prices, int initialCapital, int k) {
        int n = prices.length;

        // 定义状态数组
        int[][][] dp = new int[n][k + 1][2]; // 不持有股票的最大利润
        int[][] cash = new int[n][k + 1]; // 剩余资金

        // 初始化
        for (int j = 0; j <= k; j++) {
            dp[0][j][0] = initialCapital;
            dp[0][j][1] = (initialCapital >= prices[0]) ? initialCapital - prices[0] : Integer.MIN_VALUE;
            cash[0][j] = initialCapital;
        }

        // 遍历并更新状态
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);

                // 确保有足够的资金进行买入操作
                if (cash[i - 1][j] >= prices[i]) {
                    dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
                } else {
                    dp[i][j][1] = dp[i - 1][j][1];
                }

                // 更新剩余资金
                cash[i][j] = Math.max(cash[i - 1][j], cash[i - 1][j] - prices[i]);
            }
        }

        return dp[n - 1][k][0]; // 返回最终的最大利润
    }
    public static int maxProfit(int beginMoney, int days, int times) {
        // 初始资金
        int money = beginMoney;
        // 每一天的价格时刻 一共10天，每一天有21个价格时刻
        int[][] timePrices = {{9, 1, 4, 4, 7, 7, 7, 2, 6, 1}};// getTimePrices(days, times);
        for (int i = 0; i < times; i++) {
            System.out.print(timePrices[0][i] + ",");
        }
        // 每一天允许交易的最大次数
        int maxTradeTimes = 2;
        // 如果最大交易次数小于1，则直接返回50
        if (maxTradeTimes < 1) {
            return 50;
        } else if (maxTradeTimes == 1) {
            /*// 如果最大交易次数为1
            for (int day = 0; day < days; day++) {
                // 从第一天开始，就要追求收益最大化
                int[][][] dp = new int[times][2][2];
                // 初始化
                // 每一天开始的初始资金就是前一天的总收益
                dp[0][1][0] = beginMoney;
                dp[0][1][1] = beginMoney >= timePrices[day][0] ? beginMoney - timePrices[day][0] : Integer.MIN_VALUE;
                //填剩下的位置
                for (int i = 1; i < times; i++) {
                    // 此价格时刻没有持有股票，可能1：前一时刻我也没有持有股票，现在时刻无操作；可能2：前一时刻我持有股票，现在时刻我选择卖出。
                    dp[i][0] = Math.max(dp[i - 1][0] == Integer.MIN_VALUE ? Integer.MIN_VALUE : dp[i - 1][0], dp[i - 1][1] == Integer.MIN_VALUE ? Integer.MIN_VALUE : dp[i - 1][1] + timePrices[day][i]);
                    // 此价格时刻持有股票，可能1：前一时刻我也持有股票，现在时刻无操作；可能2：前一时刻我没有持有股票，现在时刻我选择买入。
                    dp[i][1] = Math.max(dp[i - 1][1] == Integer.MIN_VALUE ? Integer.MIN_VALUE : dp[i - 1][1], dp[i - 1][0] == Integer.MIN_VALUE ? Integer.MIN_VALUE : dp[i - 1][0] < timePrices[day][i] ? Integer.MIN_VALUE : dp[i - 1][0] - timePrices[day][i]);
                }
                beginMoney = dp[times - 1][0] == Integer.MIN_VALUE ? Integer.MIN_VALUE : dp[times - 1][0]; //在当天最后一个价格时刻，我将手里的股票卖掉的情况下能获得的最大利润
            }*/
        } else if (maxTradeTimes > 1 && maxTradeTimes <= times / 2) {
            // 如果最大交易次数大于1，小于等于无限，类似于给定一个具体的k
            for (int day = 0; day < days; day++) {
                // 从第一天开始，就要追求收益最大化
                int[][][] dp = new int[times][maxTradeTimes + 1][2];
                for (int i = 0; i < times; i++) {
                    for (int tempK = 1; tempK <= maxTradeTimes; tempK++) { //穷举k
                        if (i == 0) { //baseCase
                            dp[i][tempK][0] = beginMoney;
                            dp[i][tempK][1] = beginMoney >= timePrices[day][0] ? beginMoney - timePrices[day][0] : Integer.MIN_VALUE;
                            continue;
                        }
                        // 上一个价格时刻就没有持有，且截至上一个价格时刻最大交易次数限制为 k；然后当前价格时刻选择 rest，所以当前价格时刻我还是没有持有，最大交易次数限制依然为 k。
                        // 上一个价格时刻持有股票，且截至上一个价格时刻最大交易次数限制为 k；但是当前价格时刻我 sell 了，所以当前价格时刻我没有持有股票了，最大交易次数限制依然为 k。
                        dp[i][tempK][0] = Math.max(dp[i - 1][tempK][0], dp[i - 1][tempK][1] + timePrices[day][i]);
                        // 上一个价格时刻就持有着股票，且截至上一个价格时刻最大交易次数限制为 k；然后当前价格时刻选择 rest，所以当前价格时刻我还持有着股票，最大交易次数限制依然为 k。
                        // 上一个价格时刻本没有持有，且截至上一个价格时刻最大交易次数限制为 k - 1；但当前价格时刻我选择 buy，所以当前价格时刻我就持有股票了，最大交易次数限制为 k。
                        dp[i][tempK][1] = Math.max(dp[i - 1][tempK][1], dp[i - 1][tempK - 1][0] >= timePrices[day][i] ? dp[i - 1][tempK - 1][0] - timePrices[day][i] : Integer.MIN_VALUE);
                    }
                }
                beginMoney = dp[times - 1][maxTradeTimes][0];
            }
        } else {
            // 如果最大交易次数为无限
            for (int day = 0; day < days; day++) {
                int[][] dp = new int[times][2];
                //初始化
                dp[0][0] = beginMoney;
                dp[0][1] = beginMoney >= timePrices[day][0] ? beginMoney - timePrices[day][0] : Integer.MIN_VALUE;
                //填剩下的位置
                for (int i = 1; i < times; i++) {
                    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + timePrices[day][i]); //我今天没有持有股票，可能1：前一天我也没有持有股票，今天无操作；可能2：前一天我持有股票，今天我选择卖出。
                    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] >= timePrices[day][i] ? beginMoney - dp[i - 1][0] - timePrices[day][i] : Integer.MIN_VALUE); //我今天持有股票，可能1：前一天我也持有股票，今天无操作；可能2：前一天我没有持有股票，今天我选择买入。
                }
                beginMoney = dp[times - 1][0]; //在当天最后一个价格时刻，我将手里的股票卖掉的情况下能获得的最大利润
            }
        }
        return beginMoney == Integer.MIN_VALUE ? money : beginMoney - money;
    }

    public static void main(String[] args) {
        int i = maxProfit(2, 1, 10);
        System.out.println();
        System.out.println(i);
    }

    /**
     * 生成模拟数据
     *
     * @param days
     * @param times
     * @return
     */
    public static int[][] getTimePrices(int days, int times) {
        int[][] timePrices = new int[days][times];
        Random random = new Random();

        for (int i = 0; i < days; i++) {
            for (int j = 0; j < times; j++) {
                timePrices[i][j] = random.nextInt(10) + 1; // 生成 1 到 100 之间的随机数
            }
        }
        return timePrices;
    }


}
